/**
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 *https://leetcode.cn/problems/partition-equal-subset-sum/
 *思路：此问题可转为背包问题：给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满
 *题解：https://labuladong.gitee.io/algo/3/27/82/
 */
class CanPartition {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int num:nums) {
            sum+=num;
        }
        if(sum%2!=0) {//和为奇数时不可能划分成两个相等的子集
            return false;
        }
        sum=sum/2;
        int n=nums.length;
        boolean[][] dp=new boolean[n+1][sum+1];
        for(int i=0;i<sum;i++) {
            dp[0][i]=false;
        }
        for(int i=0;i<n;i++) {
            dp[i][0]=true;
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=sum;j++) {
                if(j-nums[i-1]<0) {//容量不足，不能转入背包
                    dp[i][j]=dp[i-1][j];
                } else {
                    dp[i][j]=(dp[i-1][j]|dp[i-1][j-nums[i-1]]);//容量足，选择装入还是不装入
                }
            }
        }
        return dp[n][sum];
    }
}